// https://www.lintcode.com/problem/longest-univalue-path/

/**
 * Definition of TreeNode:
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left, right;
 *     public TreeNode(int val) {
 *         this.val = val;
 *         this.left = this.right = null;
 *     }
 * }
 */

public class Solution {
    protected int ret;
    /**
     * @param root: 
     * @return: the length of the longest path where each node in the path has the same value
     */
    public int longestUnivaluePath(TreeNode root) {
        // Write your code here
        /*
        就像网友所说，这题easy难度的确是膨胀了...
        简说下思路：
        1. 5-5-5路径长度是2，5路径长度是0。
        2. 要处理2种情况：1）路径不经过当前节点；2）路径经过当前节点。
        */
        ret = 0;
        _longestUnivaluePath(root);
        return ret;
        
    }
    
    protected int _longestUnivaluePath(TreeNode node) {
        if (node == null) {
            return 0;
        }
        int ll = _longestUnivaluePath(node.left);
        int lr = _longestUnivaluePath(node.right);
        int to_left = 0, to_right = 0;
        if ((node.left != null) && (node.val == node.left.val)) {
            to_left = ll + 1;
        }
        if ((node.right != null) && (node.val == node.right.val)) {
            to_right = lr + 1;
        }
        ret = Math.max(ret, to_left + to_right);
        return Math.max(to_left, to_right);
    }
}